package _回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _组合 {

    class Solution {
        // 输入：n = 4, k = 2
        // 输出：
        //[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> combine(int n, int k) {
            back(n, k, 1);
            return res;
        }

        private void back(int n, int k, int startIndex) {
            if (path.size() == k) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = startIndex; i <= n; i++) {
                path.add(i);
                back(n, k, i + 1);
                path.removeLast();
            }
        }
    }

    class Solution_39 {
        // 输入：candidates = [2,3,6,7], target = 7
        // 输出：[[2,2,3],[7]]
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            dfs(candidates, target, 0);
            return ans;
        }

        private void dfs(int[] candidates, int target, int index) {

            if (target == 0) {
                ans.add(new ArrayList<>(path));
                return;
            }
            for (int i = index; i < candidates.length; i++) {
                if (target - candidates[i] >= 0) {
                    path.add(candidates[i]);
                    dfs(candidates, target - candidates[i], i); // 仍然传递当前索引i
                    path.removeLast();
                }
            }
        }
    }

    class Solution_40 {
        //  元素有重复，只能选一次
        //  输入: candidates = [10,1,2,7,6,1,5], target = 8,
        //  输出:
        //  [
        //  [1,1,6],
        //  [1,2,5],
        //  [1,7],
        //  [2,6]
        //  ]
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            dfs(candidates, target, 0);
            return res;
        }

        private void dfs(int[] candidates, int target, int index) {
            if (target == 0) {
                res.add(new ArrayList<>(path));
                return;
            }
            // index是用来控制纵向的（递归）下一个数的起始
            for (int i = index; i < candidates.length && candidates[i] <= target; i++) {
                // 在同一树层剪枝
                if (i > index &&  candidates[i] == candidates[i - 1])
                    continue;
                path.add(candidates[i]);
                dfs(candidates, target - candidates[i], i + 1);
                path.removeLast();
            }
        }
    }
    class Solution_216 {
        // 找出所有相加之和为 n 的 k 个数的组合,只能使用数字1——9
        // 输入: k = 3, n = 7
        // 输出: [[1,2,4]]
        // 解释:
        // 1 + 2 + 4 = 7
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            dfs(k, n, 0, 1);
            return res;
        }

        private void dfs(int k, int n, int sum, int Index) {
            if (path.size() == k && sum == n) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = Index; i <= 9; i++) {
                if (sum > n || path.size() > k)
                    continue;
                path.add(i);
                sum += i;
                dfs(k, n, sum, i + 1);
                path.remove(path.size() - 1);
                sum -= i;
            }
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        return null;
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        back(nums, used, res, path);
        return res;
    }

    // 46：全排列：https://leetcode.cn/problems/permutations/
    // 因为每一次都要从头开始找，所以需要一个used
    private void back(int[] nums, boolean[] used, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                back(nums, used, res, path);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }

    // 47：全排列II:https://leetcode.cn/problems/permutations-ii/
    // 一定要去画递归树理解,,写代码注意力要集中，先想清楚再写
    List<List<Integer>> res47 = new ArrayList<>();
    List<Integer> path47 = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        back47(nums, used);
        return res47;
    }

    private void back47(int[] nums, int[] used) {
        if (path47.size() == nums.length) {
            Arrays.sort(nums);
            res47.add(new ArrayList<>(path47));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
            if (used[i] == 0) {
                path47.add(nums[i]);
                used[i] = 1;
                back47(nums, used);
                path47.remove(path47.size() - 1);
                used[i] = 0;
            }
        }
    }

}



















